package com.jacky.二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 二叉树层次遍历_102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        //如果二叉树为空，那就返回一个空的List
        if(root == null) return new LinkedList<>();
        //定义一个List,用来存储遍历的结果
        List<List<Integer>> res = new ArrayList<>();
        //定义一个链表队列，用来辅助层次遍历二叉树
        Queue<TreeNode> queue = new LinkedList<>();
        //把头结点放到队列里面
        queue.add(root);
        //如果队列不为空，就遍历
        while(!queue.isEmpty()){
            //获得队列的大小,ArrayList和LinkedList求大小的方法都是size()
            int size = queue.size();
            //定义一个数组来放每一层遍历的结果
            List<Integer> list = new ArrayList<>();
            //遍历二叉树的某一层
            for(int i=0;i<size;i++){
                TreeNode cur = queue.poll();
                //取出节点值，放到list里面
                list.add(cur.val);
                //如果当前节点有左子树，则入队列
                if(cur.left != null) queue.add(cur.left);
                //如果当前节点有右子树，则入队列
                if(cur.right != null) queue.add(cur.right);
            }
            //一层遍历完之后，则放到res里面
            res.add(list);
        }
        //返回所有智
        return res;
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);

        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}
